#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define NUMBER	500000
#define FORZ(i, max)	for(i = 0; i < max; i++)
#define SUM(n) ((n)*((n)+1ll)/2ll)

typedef long long int ll;
typedef unsigned long long int ull;
typedef unsigned int uint;

unsigned int s[200000];

int cmp(const void *a, const void *b) {
	return (*(int*)a-*(int*)b);
}

int main() {
	int n,i,j,k,mul,v;
	scanf("%d",&n);
	FORZ(i,n) scanf("%u",&s[i]);
	qsort(s,n,sizeof(int),cmp);
	mul=1;i=0;
	while(i<n) {
		j=i;k=0;
		while(s[j]==s[i]) {
			k++;j++;
		}
		v=(j-i>2)?((j-i)*(j-i-1))%10000:j-i;
		//printf("%d %d\n",j-i,v);
		mul = (mul * v) % 10000;
		i=j;
	}
	mul*=2;
	printf((mul>1000)?"%04d\n":"%d\n",mul%1000);
	return 0;
}
